package com.java.comprehensive.arithmetic.leecode.easy;

import util.TreeNode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Stack;

/**
 * @Author: Dgg
 * @Date: 2021/11/28 20:24
 * 二叉树的 中序遍历
 */
public class LeetCode_94 {

	public static List<Integer> inorderTraversal(TreeNode root) {
		List<Integer> integers = new ArrayList<>();

		if (root == null) return integers;

		middleSort(root.left,integers);
		integers.add(root.val);
		System.out.print(root.val + " ");
		middleSort(root.right,integers);

		return integers;
	}

	public static void middleSort(TreeNode root, List<Integer> list) {

		Stack<TreeNode> treeNodeStack = new Stack<>();

		TreeNode node = root;

		while (node != null || !treeNodeStack.isEmpty()) {
			while (node != null) {
				treeNodeStack.push(node);
				node = node.left;
			}
			if (!treeNodeStack.isEmpty()) {

				node = treeNodeStack.pop();
				list.add(node.val);
				System.out.print(node.val + " ");
				node = node.right;
			}
		}
	}
	public void inorder(TreeNode root, List<Integer> res) {
		if (root == null) {
			return;
		}
		inorder(root.left, res);
		res.add(root.val);
		inorder(root.right, res);
	}

	public static void main(String[] args) {
		TreeNode treeNode2 = new TreeNode(2, new TreeNode(3, null, null), null);
		TreeNode treeNode = new TreeNode(1, null, treeNode2);
		System.out.println(Arrays.toString(inorderTraversal(treeNode).toArray()));
	}
}
